
public class MazeGenerator_DFS extends MazeGenerator {
	
	public static Maze generateMaze( int width, int height ) { 
		Maze maze = new Maze( width, height );
		m_buildMaze( maze );
		
		return maze;
	}

	/* This adjacency data array is used as a temporary structure when building the maze. It is not guaranteed to
	 * remain constant, or to exist after map generation has been completed. It should never be accessed externally.
	 * NOTE: This should have been locally allocated and passed through the recursive function as an argument, however
	 * due to the somewhat... interesting nature of Java's memory management and function architecture, simply passing by
	 * reference is not an option. As a result, this member variable has been implemented.
	 */
	private static char[] m_buildMazeAdjData;
	/* This integer contains the maximum depth of a recursive branch. In the recursive function, if the current depth exceeds this,
	 * value, than the buildMazeMaxDepth variable is set to be the current recursing depth. This is primarily used to determine which
	 * path is the deepest, and as a result, at the end of which path should the exit be placed.
	 */
	private static int m_buildMazeMaxDepth = 0;
	
	/* The build maze function should not be called externally, and is defined privately. 
	 * This function implements a depth first search, with randomly assigned branch directions in order
	 * to build the maze. The algorithm calls for an iteration through a stack, however it is implemented using
	 * a recursive function, using the system stack for state management. This helps keep things legible.
	 */
	private static void m_buildMaze ( Maze m ) {

		/* Clearly, the algorithm will not work with mazes size 0 to 3, as these are not large enough to contain any real data.
		 * As a result, I've hard-coded in a few edge cases for this kind of thing. If the width and height are too small, just early out.
		*/
		if ( m.getWidth() < 3 || m.getHeight() < 3 ) {
			System.out.println( "ERROR: Generated maze size must be greater than 2." );
			return;
		}
		
		if ( m.getWidth() > 100 || m.getHeight() > 100 ) {
			System.out.println( "ERROR: Generated maze size is too large." );
			return;
		}
		
		/* Because the DFS algorithm is based on a table of adjacency (rather than the grid based system in which the final
		 * maze is being stored), we define a table that is half the size, in which to store this adjacency data, and then 
		 * scale it up after generation, filling in the space between non-adjacent cells with "wall" tiles.
		 */
		int w = (int)Math.ceil( m.getWidth()/2.0 ) - 1;
		int h = (int)Math.ceil( m.getHeight()/2.0 ) - 1;
		
		m_buildMazeAdjData = new char[ w * h ];
		
		/* While it may be confusing at first, all adjacency data is stored in a single char value. This is intended to 
		 * be compact, and to eliminate the need for a separate data structure for something which is only going to be used
		 * once in a specific function.
		 *
		 * the structure for this uses bit-flags to store the adjacency data. wall Up, wall Down, wall Left, wall Right, cell visited.
		 *		// 	0	0	0	0	0	0	0	0
		 *		// 	U	D	L	R |	V	
		 *
		 * "wall left" defines that this cell is not connected to that to it's immediate left (x-1,y). "wall top" is similar,
		 * (x,y-1). The visited flag is used by the generation process, to ensure that no loops are generated in the maze, which
		 * would result in a frustrating, and "imperfect" maze.
		 */
		
		// initially populate the arrays with 11110000, An unvisited cell that is not connected to any other cell.
		for ( int i = 0; i < m_buildMazeAdjData.length; i ++ ) m_buildMazeAdjData[i] = 0b11110000;
		
		// Select a random cell on the grid to be the "start" cell. This is both the location at which the player
		// starts, and the initial call location for the recursive DFS algorithm.
		m.setStart( m_randRange( 0, w-1 ), m_randRange( 0, h-1 ) );
		//m.start_x = m_randRange( 0, w-1 );
		//m.start_y = m_randRange( 0, h-1 );
		
		// now call the recursive maze building function, starting at the start cell, with a NOOP parent adjacency flag.
		m_buildMazeRecurse( m, m.getStartX(), m.getStartY(), w, h, -1, 0 );
	
		/* Now that the maze adjacency table has been calculated, it is time to fill the final maze data structure. This is
		 * done simply by iterating through the adjacency table, and creating paths at the coordinate, doubled to accommodate space
		 * for the walls. Then, the adjacency flags on either side are checked. If the wall flag for right is true, then there is
		 * a wall between this cell and the next on the right hand side. Because of this, tile (2x+1,2y) will be set to be a wall.
		 */
		
		// NOTE: This is set to add 1 to each coordinate, so that there is an outer wall on the left hand side. If this was not the case,
		// the maze path would begin on tile 0, and there would not be a wall on the outside.
		
		// initialize the data (final maze) array with walls by default.
		for ( int i = 0; i < m.getWidth() * m.getHeight(); i ++ )
			m.setTile( i, MazeTile.WALL );
			//m.data[i] = MazeTile.WALL;
		
		// now that we've got the wall configuration built in the adjacency data, fill it into the maze grid we have.
		for ( int x = 0; x < w; x ++ ) {
			for ( int y = 0; y < h; y ++ ) {
				// Set the tile at (2x,2y) to be a path.
				int x2 = x*2 + 1;
				int y2 = y*2 + 1;
				
				//m.data[ m_index(x2,y2) ] = MazeTile.PATH;
				m.setTile( x2, y2, MazeTile.PATH );
				
				// To ensure that walls are not placed in the way of the path due to the coordinate clamping,
				// check to ensure that the Y coordinate is greater than zero.
				if ( y > 0 ) {
					// Check the adjacency flag for the top side,
					if ( (m_buildMazeAdjData[ m_index(x,y,w,h) ] & (char)0b10000000) != 0 )
						// if the flag is set to 1, then there is a wall between this cell and the next.
						//m.data[ m_index(x2,y2-1) ] = MazeTile.WALL;
						m.setTile(x2, y2-1, MazeTile.WALL);
					else
						// otherwise, this tile is a path.
						//m.data[ m_index(x2,y2-1) ] = MazeTile.PATH;
						m.setTile(x2, y2-1, MazeTile.PATH);
				}
				
				// The same can be done with the bottom side.
				if ( (m_buildMazeAdjData[ m_index(x,y,w,h) ] & (char)0b01000000) != 0 )
					//m.data[ m_index(x2,y2+1) ] = MazeTile.WALL;
					m.setTile(x2, y2+1, MazeTile.WALL);
				else
					//m.data[ m_index(x2,y2+1) ] = MazeTile.PATH;
					m.setTile(x2, y2+1, MazeTile.PATH);
				
				// And do the same on the X axis.
				if ( x > 0 ) {
					if ( (m_buildMazeAdjData[ m_index(x,y,w,h) ] & (char)0b00100000) != 0 )
						//m.data[ m_index(x2-1,y2) ] = MazeTile.WALL;
						m.setTile(x2-1, y2, MazeTile.WALL);
					else
						//m.data[ m_index(x2-1,y2) ] = MazeTile.PATH;
						m.setTile(x2-1, y2, MazeTile.PATH);
				}
				
				if ( (m_buildMazeAdjData[ m_index(x,y,w,h) ] & (char)0b00010000) != 0 )
					//m.data[ m_index(x2+1,y2) ] = MazeTile.WALL;
					m.setTile(x2+1, y2, MazeTile.WALL);
				else
					//m.data[ m_index(x2+1,y2) ] = MazeTile.PATH;
					m.setTile(x2+1, y2, MazeTile.PATH);
			}
		}
	
		// lastly, scale up the start and end location to match the 2X coordinate system. (as they were generated in
		// the half sized coordinate system.
		//m.start_x = m.start_x*2 + 1;
		//m.start_y = m.start_y*2 + 1;
		m.setStart( m.getStartX() * 2 + 1, m.getStartY() * 2 + 1 );
		
		//m.exit_x = m.exit_x*2 + 1;
		//m.exit_y = m.exit_y*2 + 1;
		m.setExit( m.getExitX() * 2 + 1, m.getExitY() * 2 + 1 );
		
		// After this is complete, the array m_buildMazeAdjData should be freed, and all relevant data is stored in 
		// the data array. Because Java is memory managed, we'll have to trust that the garbage collecter will free
		// this data eventually, rather than being allowed to free it ourselves.
		m_buildMazeAdjData = null;
	}
	

	/* This function exists for the sake of convenience. Because a bit flag must be removed for two cells whenever
	 * a "wall" is removed, this function takes two cells, and sets the flag to zero for the two opposite sides, such
	 * that the two of them are "connected". NOTE: this function assumes the coordinates of the cells are only 1 unit
	 * away in a single direction.
	 */
	private static void m_buildMazeDestroyWall ( int x, int y, int x2, int y2, int w, int h ) {
		if ( x2 > x ) {
			m_buildMazeAdjData[ m_index(x,y,w,h) ] = (char)(m_buildMazeAdjData[ m_index(x,y,w,h) ] & 0b11101111 );
			m_buildMazeAdjData[ m_index(x2,y2,w,h) ] = (char)(m_buildMazeAdjData[ m_index(x2,y2,w,h) ] & 0b11011111 );
		}else if ( x2 < x ) {
			m_buildMazeAdjData[ m_index(x,y,w,h) ] = (char)(m_buildMazeAdjData[ m_index(x,y,w,h) ] & 0b11011111 );
			m_buildMazeAdjData[ m_index(x2,y2,w,h) ] = (char)(m_buildMazeAdjData[ m_index(x2,y2,w,h) ] & 0b11101111 );
		}
		
		if ( y2 > y ) {
			m_buildMazeAdjData[ m_index(x,y,w,h) ] = (char)(m_buildMazeAdjData[ m_index(x,y,w,h) ] & 0b10111111 );
			m_buildMazeAdjData[ m_index(x2,y2,w,h) ] = (char)(m_buildMazeAdjData[ m_index(x2,y2,w,h) ] & 0b01111111 );
		}else if ( y2 < y ) {
			m_buildMazeAdjData[ m_index(x,y,w,h) ] = (char)(m_buildMazeAdjData[ m_index(x,y,w,h) ] & 0b01111111 );
			m_buildMazeAdjData[ m_index(x2,y2,w,h) ] = (char)(m_buildMazeAdjData[ m_index(x2,y2,w,h) ] & 0b10111111 );
		}
	}
	
	/* This recursive function is the actual implementation of the DFS maze generation code.
	 * While the algorithm itself is specified to use a visited cells stack, it is more intuitive to use a recursive
	 * function call, using the system stack instead. This function should never be called from any external source, as
	 * it has the potential to corrupt the maze data when not used correctly.
	 */
	private static void m_buildMazeRecurse ( Maze m, int x, int y, int w, int h, int pdflag, int depth ) {
		// The first step in this algorithm, is to ensure that no previously visited cell be re-visited, to avoid loops
		// in the maze. Simply return if the visited flag has been set in the adjacency data.
		if ( (m_buildMazeAdjData[ m_index(x,y,w,h) ] & 0b00001000) != 0 ) return;
		
		// Now mark the current cell as visited.
		m_buildMazeAdjData[ m_index(x,y,w,h) ] = (char)(m_buildMazeAdjData[  m_index(x,y,w,h) ] | 0b00001000);
				
		/* The following code block essentially ensures that the exit location is the MAXIMUM possible distance away from
		 * the entrance location within the maze, by keeping a recurse travel depth, and checking against an object-wide record.
		 * Again, this probably could have been a pass-by-reference parameter, but unfortunately Java is weird... 
		 */
		// Check if the current recurse depth is greater than the previous max.
		if ( depth > m_buildMazeMaxDepth ) {
			// set the max value to be the current depth
			m_buildMazeMaxDepth = depth;
			// Set the exit location to be the active cell.
			m.setExit(x, y);
			//m.exit_x = x;
			//m.exit_y = y;
		}
		
		// Check the "parent direction flag" (bdFlag), which indicates the direction in which the parent function call
		// recursed. This determines which wall should be removed from the maze adjacency data.
		switch (pdflag) {
			case 0:
				// If the parent direction flag is set to "up", remove the wall between this cell, and the one below.
				m_buildMazeDestroyWall( x, y, x, y+1, w, h );
				break;
			case 1:
				// If the parent direction flag is "down", remove the wall between this cell, and the one above.
				m_buildMazeDestroyWall( x, y, x, y-1, w, h );
				break;
			case 2:
				// The same case is given here for "left"
				m_buildMazeDestroyWall( x, y, x+1, y, w, h );
				break;
			case 3:
				// The next is given for "right".
				m_buildMazeDestroyWall( x, y, x-1, y, w, h );
				break;
			default:
				// Lastly, if no valid parent direction is specified, optionally print a message.
				//System.out.println( "Parent direction flag " + pdflag + " could not be matched" );
				break;
		}
		
		/* Because this depth first search algorithm is designed to exhaust all grid cells, it is important to not only
		 * select a random direction in which to recurse, but also to ensure that every direction is tried at some point.
		 * In order to accomplish this, a simple method is used... a list of all directions (up, down, left, right) is made,
		 * and scrambled using swaps. Then this list is iterated through in order to recurse in all directions.
		 */
		int[] dir = {0,1,2,3};
		for ( int i = 0; i < 4; i ++ ) {
			int tmp; int a = m_randRange( 0, 3 ); int b = m_randRange( 0, 3 );
			tmp = dir[a]; dir[a] = dir[b]; dir[b] = tmp;
		}
		
		// now iterate through the list of directions, calling build maze function recursively, and passing the current direction
		// as the pdflag value.
		for ( int i = 0; i < dir.length; i ++ ) {
			switch ( dir[i] ) { 
			case 0:// recurse upwards.
				m_buildMazeRecurse( m, x, y-1, w, h, 0, depth+1 );
				break;
			case 1: //  recurse downwards.
				m_buildMazeRecurse( m, x, y+1, w, h, 1, depth+1 );
				break;
			case 2: // recurse left.
				m_buildMazeRecurse( m, x-1, y, w, h, 2, depth+1 );
				break;
			case 3: //  recurse right.
				m_buildMazeRecurse( m, x+1, y, w, h, 3, depth+1 );
				break;
			}
		}
	}
	

	/* The m_randRange function is simply a utility function to return a random number within the range specified from min to max.
	 * nothing fancy.
	 */
	private static int m_randRange ( int min, int max ) {
		return min + (int)(Math.random() * ((max - min) + 1));
	}
	
	/* The m_index function clamps a set of coordinates to a range between 0 and w/h.
	 * Then, it returns the index into a 2D array specified at y * width + x.
	 */
	private static int m_index ( int x, int y, int w, int h ) {
		if ( x < 0 ) x = 0;
		if ( x >= w ) x = w-1;
		if ( y < 0 ) y = 0;
		if ( y >= h ) y = h-1;
		
		return y * w + x;
	}
}
